Search results for "Logical equivalence"
showing 8 items of 8 documents
Caractérisation des flots d' Anosov en dimension 3 par leurs feuilletages faibles
1995
AbstractWe consider Anosov flows on closed 3-manifolds. We show that if such a flow admits a weak foliation whose lifting in the universal covering is a product foliation, thenit is characterized up to topological equivalence by its weak stable foliation up to topological conjugacy. As a corollary we obtain that, up to topological equivalence and finite coverings, suspensions and geodesic flows are the unique Anosov flows on closed 3-manifolds whose weak stable foliations are transversely projective.
Logics with counting and equivalence
2014
We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NEXPTIME-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.
Two-Variable First-Order Logic with Equivalence Closure
2012
We consider the satisfiability and finite satisfiability problems for extensions of the two-variable fragment of first-order logic in which an equivalence closure operator can be applied to a fixed number of binary predicates. We show that the satisfiability problem for two-variable, first-order logic with equivalence closure applied to two binary predicates is in 2-NExpTime, and we obtain a matching lower bound by showing that the satisfiability problem for two-variable first-order logic in the presence of two equivalence relations is 2-NExpTime-hard. The logics in question lack the finite model property; however, we show that the same complexity bounds hold for the corresponding finite sa…
Local Normal Forms for First-Order Logic with Applications to Games and Automata
1999
Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…
Precision, Applicability, and Economic Implications: A Comparison of Alternative Biodiversity Offset Indexes
2021
AbstractThe rates of ecosystem degradation and biodiversity loss are alarming and current conservation efforts are not sufficient to stop them. The need for new tools is urgent. One approach is biodiversity offsetting: a developer causing habitat degradation provides an improvement in biodiversity so that the lost ecological value is compensated for. Accurate and ecologically meaningful measurement of losses and estimation of gains are essential in reaching the no net loss goal or any other desired outcome of biodiversity offsetting. The chosen calculation method strongly influences biodiversity outcomes. We compare a multiplicative method, which is based on a habitat condition index develo…
Games and Bisimulations for Intuitionistic First-Order Kripke Models
2021
The aim of this paper is to introduce the notion of a game for intuitionisticfirst-order Kripke models. We also establish links between notions presented here and thenotions of logical equivalence and bounded bisimulation for intuitionistic first-order Kripkemodels, and the Ehrenfeucht–Fra ̈ıss ́e game for classical first-order structures.
Flots de Smale en dimension 3: présentations finies de voisinages invariants d'ensembles selles
2002
Abstract Given a vector field X on a compact 3-manifold, and a hyperbolic saddle-like set K of that vector field, we consider all the filtering neighbourhood of K: by such, we mean any submanifold which boundary is tranverse to X, the maximal invariant of which is equal to K and which intersection with every orbit of X is connected. Up to topological equivalence, there is only a finite number of such neighbourhoods. We give a finite combinatorial presentation of the global dynamics on any such neighbourhood. A key step is the construction of a unique model of the germ of X along K; this model is, roughly speaking, the simplest three-dimensional manifold and the simplest Smale flow exhibitin…
On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations
2009
We show that every finitely satisfiable two-variable first-order formula with two equivalence relations has a model of size at most triply exponential with respect to its length. Thus the finite satisfiability problem for two-variable logic over the class of structures with two equivalence relations is decidable in nondeterministic triply exponential time. We also show that replacing one of the equivalence relations in the considered class of structures by a relation which is only required to be transitive leads to undecidability. This sharpens the earlier result that two-variable logic is undecidable over the class of structures with two transitive relations.